package com.demo416_分割等和子集;

import java.util.Arrays;

/**
 * 把一个数组分为和相等的2个子集
 *
 * 这个和把一个数组分成k个相等的子集是一样的做法:
 *
 * 那就是取2个桶, 每个桶的容量 刚好是这个所有元素和的一半.
 *
 * 分别遍历所有的元素, 看看是不是刚好可以放下所有的元素, 如果可以则是true,  否则是false
 *
 * 超时了!!!!!
 */
public class Solution_动态规划 {
    public boolean canPartition(int[] nums) {
        // 排序
        Arrays.sort(nums);
        // 求和
        int sum = Arrays.stream(nums).sum();
        // 求均值
        int average=sum/2;
        // 特判1
        if (sum%2!=0){
            return false;
        }
        // 特判2
        if (nums[nums.length-1]>average){
            return false;
        }
        // 创建2个桶
        int[] buckets = new int[2];
        Arrays.fill(buckets,average);

        // 递归
        //boolean result = dfs(nums,buckets,0);

        //
       return true;

    }


}
